package Other.MAXPathSum;

//124. 二叉树中的最大路径和
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

/**
 *  +A的函数返回包含当前节点的最大值
 *  在计算过程中记录以当前节点为根的值,与当前最大值进行比较
 * 
 */
class Solution {
    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root){
        if(root==null) return 0;
        maxPathSumA(root);
        return ans;
    }

    public int maxPathSumA(TreeNode root) {
        int left = Integer.MIN_VALUE;
        int right = Integer.MIN_VALUE;
        if(root.left!=null){
            left = maxPathSumA(root.left);
        }
        if(root.right!=null){
            right = maxPathSumA(root.right);
        }
        int maxChild = Math.max(left, right);
        int maxAllChild = maxChild;
        if(maxChild>0&&left>0&&right>0){
                maxAllChild+= (left==maxChild?right:left);
        }
        int curMax = root.val;
        if(maxAllChild>0) curMax+=maxAllChild;
        ans =  Math.max(ans,Math.max(left, Math.max(right, curMax)));
        return maxChild>0?maxChild+root.val:root.val;
    }
}